package interview.hw_od;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 跳房子II https://codefun2000.com/p/P1349
 */
public class Hopscotch2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] split = s.substring(1, s.length() - 1).split(",");
        //使用一个二维数组记录值及其原始索引
        int[][] nums = new int[split.length][2];
        for (int i = 0;i < nums.length;i++) {
            nums[i][0] = Integer.parseInt(split[i]);
            nums[i][1] = i;
        }
        //将二维数组按照值大小升序排序，默认是稳定排序，故值相同的情况下按索引升序排序
        Arrays.sort(nums, (n1, n2) -> n1[0] - n2[0]);

        int target = Integer.parseInt(sc.nextLine());
        int minIndex = Integer.MAX_VALUE;
        int[] result = new int[3];//使用一个数组记录结果的三个索引
        //使用三数之和的方法搜索，与三数之和不同的是不需要过滤重复值，因此每次只需要移动一个指针
        for (int i = 0;i < nums.length-2;i++) {
            int j = i+1, k = nums.length-1;
            while (j < k) {
                int sum = nums[i][0] + nums[j][0] + nums[k][0];
                if (sum == target) {
                    //1. 若相等则找到了一组，更新结果。并将k指针向中间移动，以期获得相邻相同值的情况下更小的索引值
                    if (minIndex > nums[i][1] + nums[j][1] + nums[k][1]) {
                        minIndex = nums[i][1] + nums[j][1] + nums[k][1];
                        result[0] = nums[i][1];
                        result[1] = nums[j][1];
                        result[2] = nums[k][1];
                    }
                    k--;
                } else if (sum < target) j++;//2. 若小于则需将j指针向右移动
                else k--;//3. 若大于则需将k指针向左移动
            }
        }
        Arrays.sort(result);
        System.out.printf("[%s,%s,%s]", split[result[0]], split[result[1]], split[result[2]]);
    }
}
